// 一维dp表示自低向上子问题，不需要递归处理
package main

import "fmt"
//1,1,2,3,5
func main() {
	v := fib(6)
	fmt.Println(v)
}

// fn(n) =fn(n-1)+fn(n-2)
func fib(n int) int {
	if n <= 2 {
		return 1
	}

	if n == 3 {
		return 2
	}

	a, b, c := 1, 1, 2
	for i := 4; i <= n; i++ {
		a = b 
		b = c 
		c = a + b
	}

	return c
}
